(define (node l v r) (cons l (cons v (cons r '()))))
(define (left node) (car node))
(define (right node) (car (cdr (cdr node))))
(define (value node) (car (cdr node)))

(define (add t v)
  (if (null? t)
      (node '() v '())
      (if (= v (value t))
          t
          (if (< v (value t))
              (node (add (left t) v) (value t) (right t))
              (node (left t) (value t) (add (right t) v))))))

(define (remove t v)
  (if (null? t)
      t
      (if (= v (value t))
          (if (if (null? (left t))
                  (null? (right t))
                  #f)
              '()
              (if (null? (left t))
                  (right t)
                  (if (null? (right t))
                      (left t)
                      (rotate (left t) (lambda (x) x) (right t)))))
          (if (< v (value t))
              (node (remove (left t) v) (value t) (right t))
              (node (left t) (value t) (remove (right t) v))))))

(define (rotate t parent tree-right)
  (if (null? (right t))
      (node (parent (left t)) (value t) tree-right)
      (rotate (right t) (lambda (hole) (parent (node (left t) (value t) hole))) tree-right)))

(define (contains? t v)
  (if (null? t)
      #f
      (if (= v (value t))
          #t
          (if (< v (value t))
              (contains? (left t) v)
              (if (> v (value t))
                  (contains? (right t) v)
                  #f)))))

(define (->list-aux t m)
  (if (null? t)
      m
      (let* ((r (->list-aux (right t) m))
             (c (cons (value t) r)))
        (->list-aux (left t) c))))

(define (->list t) (->list-aux t '()))

(define (fold-aux fn t m)
  (if (null? t)
      m
      (let* ((l (fold-aux fn (left t) m))
             (c (fn l (value t))))
        (fold-aux fn (right t) c))))

(define (fold fn init t)
  (fold-aux fn t init))

(define (union a b)
  (fold (lambda (m c) (add m c)) a b))

(define (subtract a b)
  (fold (lambda (m c) (remove m c)) a b))

(define empty '())

(define t1 (add (add empty 1) 2))
(define t2 (remove t1 1))
(define t3 (union t1 t2))
(define t4 (add t3 3))
(define t5 (fold (lambda (x y) (+ x y)) 0 t4))
(define t6 (print t5))
